package com.sx.sx1.lintcode.day717;

import java.util.*;
public class LC472_vip {


   static   class ParentTreeNode {
          public int val;
         public ParentTreeNode parent, left, right;
     }


    static class Solution {
        /**
         * @param root: the root of binary tree
         * @param target: An integer
         * @return: all valid paths
         *          we will sort your return value in output
         */
        public List<List<Integer>> binaryTreePathSum3(ParentTreeNode root, int target) {
            //可以DFS套DFS，外层DFS枚举每个点为出发点，
            // 内层DFS枚举所有从出发点出发的路径，如果和为t了则将路径记录一下。代码如下：
            //原文链接：https://blog.csdn.net/qq_46105170/article/details/120094145
            List<List<Integer>> ans = new ArrayList<>();
            dfs1(root,new ArrayList<>(),ans,target);
            return ans;
        }

        public void dfs1(ParentTreeNode cur,List<Integer> ll,List<List<Integer>> ans,int target){
            if(cur ==null) return;
            dfs2(cur,cur,0,ll,ans,target);
            dfs1(cur.left,ll,ans,target);
            dfs1(cur.right,ll,ans,target);
        }
        public void dfs2(ParentTreeNode cur,ParentTreeNode from,int sum,List<Integer> ll,
                         List<List<Integer>> ans,int target){
            if(cur ==null) return;
            sum+=cur.val;
            ll.add(cur.val);
            if(sum ==target) ans.add(new ArrayList<>(ll));

            //不走回头路
            if(cur.left!=from) dfs2(cur.left,cur,sum,ll,ans,target);
            if (cur.right != from) dfs2(cur.right,cur,sum,ll,ans,target);
            if(cur.parent!=from) dfs2(cur.parent,cur,sum,ll,ans,target);
            ll.remove(ll.size()-1); //恢复现场
        }

    }

    public static void main(String[] args) {
        ParentTreeNode node1 = new ParentTreeNode();
        node1.val=1;
        ParentTreeNode node2 = new ParentTreeNode();
        node2.val=2;
        ParentTreeNode node3 = new ParentTreeNode();
        node3.val=3;
        ParentTreeNode node4 = new ParentTreeNode();
        node4.val=4;

        node1.left = node2;
        node1.right=node3;
        node2.left =node4;

        node2.parent=node1;
        node3.parent=node1;
        node4.parent=node2;
        Solution s = new Solution();
        System.out.println(s.binaryTreePathSum3(node1,6));
    }



    static class Solution1 {
        /*
         * @param root: the root of binary tree
         * @param target: An integer
         * @return: all valid paths
         */
        public List<List<Integer>> binaryTreePathSum3(ParentTreeNode root, int target) {
            // write your code here
            List<List<Integer>> res = new ArrayList<>();
            dfs1(root, new ArrayList<>(), res, target);
            return res;
        }

        void dfs1(ParentTreeNode cur, List<Integer> list, List<List<Integer>> res, int target) {
            if (cur == null) {
                return;
            }

            dfs2(cur, cur, 0, list, res, target);
            dfs1(cur.left, list, res, target);
            dfs1(cur.right, list, res, target);
        }

        void dfs2(ParentTreeNode cur, ParentTreeNode from, int sum, List<Integer> list, List<List<Integer>> res, int target) {
            if (cur == null) {
                return;
            }

            sum += cur.val;
            list.add(cur.val);
            if (sum == target) {
                res.add(new ArrayList<>(list));
            }

            // 不走回头路
            if (cur.left != from) {
                dfs2(cur.left, cur, sum, list, res, target);
            }
            if (cur.right != from) {
                dfs2(cur.right, cur, sum, list, res, target);
            }
            if (cur.parent != from) {
                dfs2(cur.parent, cur, sum, list, res, target);
            }

            list.remove(list.size() - 1);
        }
    }

   static class ParentTreeNode1 {
        int val;
        ParentTreeNode parent, left, right;

        public ParentTreeNode1(int val) {
            this.val = val;
        }
    }

}


/*
LintCode-Logo
学习
刷题
内推
VIP
其他...
搜索题目、标签、题集
邀请有礼
中文
avatar
您有199条未读消息，请及时查看
472 · 二叉树的路径和 III
算法
困难
通过率
54%

题目
题解23
笔记
讨论99+
排名
记录
描述
给一棵二叉树和一个目标值，找到二叉树上所有的和为该目标值的路径。路径可以从二叉树的任意节点出发，任意节点结束。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例 1:

输入：{1,2,3,4},6
输出：[[2, 4],[2, 1, 3],[3, 1, 2],[4, 2]]
解释：
该树如下：
    1
   / \
  2   3
 /
4
样例 2:

输入：{1,2,3,4},3
输出：[[1,2],[2,1],[3]]
解释：
该树如下：
    1
   / \
  2   3
 /
4
标签
相关题目

246
二叉树的路径和 II
中等

376
二叉树的路径和
简单

614
二叉树的最长连续子序列 II
中等

863
二叉树的路径和IV
中等
推荐课程

系统设计 System Design 2024版
数据库、API、GFS、视频流等16大系统设计详解，实战练习拿下面试/晋升“拦路虎”
已开启智能提示
发起考试
45 分 00 秒


 控制台
 历史提交

 */